\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{listings}
\usepackage{hyperref}
\usepackage{mathtools}
\usepackage{amsmath}
\usepackage{url}

\lstset{
language=MATLAB,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                   % adds a frame around the code
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
}

\title{CS 4830 Cryptography: Assignment 5} 
\author{Yifan Tong, yt347} 
\date{December 04, 2010}

\begin{document} 
\maketitle 
\newpage
\section{Problem 1} % (fold)
\label{sec:problem_1}
\subsection{CPA}
(Consulted article in footnote)%
\footnote{El Gama Encryption Scheme, UCSD Cryptography Wikipedia, \url{http://crypto.cs.uiuc.edu/wiki/index.php/Elgamal_encryption_scheme}%
}\\\\
For contradiction, assume El Gamal is not CPA-secure, and $\exists$ an adversary A that distinguishes El Gamal CPA distributions w.p. $\geq \frac{1}{2}+ \epsilon$. We now construct B to distinguish DDH tuples from random tuples.\\\\
On input $(g^a,g^b,g^c)$, we must distinguish whether $c$ is random, or $c = ab$.
\begin{enumerate}
\item Give $g^a$ to A as the public key.
\item When A outputs a challenge $(m_0,m_1)$, select random R and give $(g^b,mRg^c)$ as the response.
\item If A guesses R correctly, output 1, otherwise output 0.
\end{enumerate}
If A breaks El Gamal w.p. $\geq \frac{1}{2}+\epsilon$, then B breaks DDH  $\geq \epsilon$.  Therefore, we have a contradiction, and therefore, El Gamal is CPA-secure.
\subsection{CCA-1}
(Consulted article in footnote)%
\footnote{Helger Lipmaa, On the CCA1-Security of Elgamal and
Damgard's Elgamal, Cybernetica AS, Estonia, \url{http://www.utdallas.edu/~muratk/courses/crypto07_files/elgamal.pdf}%
}\\\\
We need to first relax the assumption of DDH to include the CDH (Computational Diffie-Hellman) assumption, with which we define the following:
\begin{eqnarray*}
cdh(g, g^x, g^y) &\equiv& g^{xy}\\
csdh_{(g, g^x)} &\equiv& cdh(g, g^x, g^y) = g^{xy})
\end{eqnarray*}
We call $csdh$ static cdh, which is an oracle function with $(g, g^x)$ fixed.\\\\
Assume El Gamal is not CCA-1 secure, then there exists adversary A that distinguishes two distributions with probability $\geq \frac{1}{2} + \epsilon$; and we use this A to construct B that breaks DDH.\\\\
We construct the following game:
\begin{tabbing}
gen\=erat\=e new keypair: $(sk=a\leftarrow Z_q, pk\leftarrow g^{sk})$\\
when $pk$ is sent to B, B forwards $pk$ as input to A\\\\
Query phase:\\
\> A asks $Dec(c_1, c_2)$ where $c_1$ and $c_2$ are chosen randomly\\
\>if $c_1\not\in G$ or $c_2\not\in G$\\
\>\>R rejects query\\
\>else\\
\>\>$c_3\leftarrow csdh(c_1)$\\
\>\>return $\frac{c_2}{c_3}$\\\\
Challenge phase:\\
\>A outputs $(m^*_0, m^*_1)$\\
\>B asks for challenge from challenger: challenger sets $b_B\leftarrow\{0, 1\}; y^*\leftarrow Z_q; h^*_1\leftarrow g^{y^*}$\\
\>if $b_R = 0$\\
\>\>$h^*_2\leftarrow G$\\
\>else\\
\>\>$h^*_2\leftarrow g^{ay^*}$\\
\>B picks random $b_B\leftarrow\{0, 1\}$, sends $(h^*_1, m_{b_A}\cdot h^*_2)$ to A\\
\>A returns $b'_A$\\\\
Guessing phase:\\
\>If $b'_A = b_A$\\
\>\>B returns 1\\
\>else\\
\>\>B returns 0
\end{tabbing}
It is important to note that the above construction satisfies the CCA-1 restriction, because A only calls Dec with random inputs \emph{before} the messages are chosen.\\\\
It is easy to see that, if A breaks El Gamal, then B breaks the DDH assumption w.p. $\geq \epsilon$.  Therefore, El Gamal is CCA-1 secure.
\subsection{CCA-2}
El Gamal is not CCA-2 secure.\\\\
An attacker can construct $c'_1$, and $c'_2$ as follows (select a random r):
\begin{eqnarray*}
c'_1 &=& c_1(h^r) = h^{(b+r)}\\
c'_2 &=& c_2(h^a)^r = h^{ab}h^{ar}m = h^{a(b+r)}m
\end{eqnarray*}
Since $(c'_1, c'_2)\neq(c_1, c_2)$, a call to $Dec$ with $(c'_1, c'_2)$ reveals $m$ completely:
\[Dec(c'_1, c'_2) = \frac{h^{a(b+r)m}}{h^{a(b+r)}} = m\]
The simple constructions above showcase a counterexample to El Gamal being CCA-2-secure, as it allows us to distinguish the distributions with a probability of 100\%  Therefore, El Gamal is \textbf{not} CCA-2 secure.
% section problem_1 (end)

\section{Problem 2} % (fold)
\label{sec:problem_2}
\subsection{Part a: Encrypt-and-MAC}
Given a secure message authentication code (G, Tag, Ver), construct another secure MAC, (G, Tag', Ver').\\\\
Construct  $Tag'(M)$ as follows:
\begin{itemize}
\item parse $M = x || M_{2\ldots n}$ where $M_{2\ldots n}$ denotes the bits between the second and last digit.
\item return $x||Tag(M_{2\ldots n})$
\end{itemize}
Construct $Ver'(M, \sigma)$ as follows:
\begin{itemize}
\item parse $M = x || M_{2\ldots n}$
\item parse $\sigma = s || \sigma_{2\ldots n}$
\item if $s = x$ and $Ver(M_{2\ldots n}, \sigma_{2\ldots n}) = 1$, return $1$; otherwise, return $0$.
\end{itemize}
This new MAC is secure because we assumed the original MAC is secure, and $\frac{1}{p(n-1)} = \epsilon$.\\\\
Given the construction above, an attacker can inquire the encryption oracle with messages $M_b$ where $b\in\{0, 1\}$, such that $M_0$ begins with $0$ and $M_1$ begins with $1$.  The oracle returns back cyphertext $(C, s||\sigma_{2\ldots n})$, where $s$ is the first bit of $M_b$.  As a result, Encrypt-and-MAC is not CPA secure, as the attacker can immediately distinguish between cyphertexts with only access to $Enc$; and therefore, \textbf{not} CCA-2 secure.
\subsection{Part b: MAC-then-Encrypt}
A simple observation tells us that MtE is only as strong as the CPA-secure $Enc$, and is therefore \textbf{not} guaranteed to be CCA-2 secure.\\\\
Given the malleable El Gamal encryption scheme outlined in Q1, it is easy to construct a new cyphertext $C'$ from original cyphertext $C$ as shown in the CCA2 section.\\\\
After obtaining $M = m|Tag(m)$ from $Dec$ with the new cyphertext $C'$, it is guaranteed that $Ver(m, Tag(m))$ returns 1, as we left both the message and the signature unmodified.
\subsection{Part c: Encrypt-then-MAC}
(Consulted article in footnote)%
\footnote{Alexandra Boldyreva, Gorgia Tech CS 6260 course notes, \url{http://www.cc.gatech.edu/~aboldyre/teaching/Fall05cs6260/Authenc.pdf}%
}\\\\
Assume for contradiction that EtM is not CCA-2 secure.  Therefore, there exists an adversary A that breaks EtM w.p. $\geq \epsilon$.\\\\
Construct adversary B that breaks CPA-secure (Gen, Enc, Dec) as follows:
\begin{tabbing}
Run \=A un\=til A halts and returns $b\in\{0, 1\}$\\ 
\>on query $Oracle(M_0, M_1)$\\
\>\>$c\leftarrow Oracle(M_0, M_1)$\\
\>\>$\sigma \leftarrow Tag(c)$\\
\>\>send $(c, \sigma)$ to $A$\\
return b
\end{tabbing}
\begin{tabbing}
Run \=A un\=til A halts\\ 
\>on query $Enc(M)$\\
\>\>$c'\leftarrow Enc(M)$\\
\>\>$\sigma' \leftarrow Tag(c)$\\
\>\>send $(c', \sigma')$ to $A$\\
\>on query $Ver(M, \sigma)$\\
\>\>$v\leftarrow Ver(M, \sigma)$\\
\>\>send $v$ to $A$
\end{tabbing}
The first part of the construction handles Oracle requests, while the second part of the construction handles $Enc$ and $Ver$ requests for adversary $B$.\\\\
Given the constructions above, it is easy to see that B breaks the CPA contract w.p. $\geq \epsilon$.  Therefore, we have a contradiction; and therefore, EtM is CCA2-secure.
% section problem_2 (end)
\section{Problem 3} % (fold)
\label{sec:problem_3}
Similar to the construction outlined in class:\\\\
Gen($1^n$): For $i = 1$ to $n$, and $b = 0, 1$, pick $x^i_b\leftarrow U_n$.  Output the keys:
\begin{eqnarray*}
\mbox{sk} &=& \left( \begin{array}{cccc}
x^1_0 & x^2_0 & \ldots & x^n_0 \\
x^1_1 & x^2_1 & \ldots & x^n_1 \end{array} \right)\\
\mbox{pk} &=& \left( \begin{array}{cccc}
h(x^1_0) & h(x^2_0) & \ldots & h(x^n_0) \\
h(x^1_1) & h(x^2_1) & \ldots & h(x^n_1) \end{array} \right)
\end{eqnarray*}
Sign$_{sk}$: For $i = 1$ to $n$, $\sigma_i\leftarrow x^i_{m_i}$. Output $\sigma=(\sigma_1,\ldots,\sigma_n)$.\\\\
Ver$_{pk}$: Output \emph{accept} iff $h(\sigma_i) = h(x^i_{m_i})$ for all $i\in\{1, n\}$.\\\\
Since $h(\cdot)$ is a CRH, it is by definition, indistinguishable from OWF; therefore, (Gen, Sign, Ver) is one-time secure by \textbf{Theorem 137.2} in lecture notes.
\subsection{Case 1: $(m', \sigma')$}
This is the case where A outputs $(m', \sigma')$ such that A did not query $m'$ nor $\sigma'$ on Sign.  If Ver accepts input $(m', \sigma')$, it then breaks the contract of (Gen, Sign, Ver) being one-time secure.  Therefore, A cannot produce a valid $(m', \sigma') pair$.\\\\
This is the case handled in the proof section of \textbf{Theorem 137.2} in lecture notes, and is therefore omitted.
\subsection{Case 2: $(m, \sigma')$}
This is the case where A outputs $(m, \sigma')$ such that A did not query $\sigma'$ on Sign.\\\\
By our construction, Ver outputs \emph{accept} iff $h(\sigma_i) = h(x^i_{m_i})$ for all $i\in\{1, n\}$.  Therefore, for Ver to output \emph{accept}, both $h(\sigma)$ and $h(\sigma')$ must be equivalent to $h(m)$, and this is a violation of the collision resistant property of the hash function.  Therefore, A cannot produce a valid $(m, \sigma')$ pair.
% section problem_3 (end)


\section{Problem 4} % (fold)
\label{sec:problem_4}
% section problem_4 (end)
\begin{itemize}
\item Sender has three messages: $\{m_1, m_2, m_3\}$.
\item Receiver has an index, $i$, indicating the message that he wishes to receive without sender learning $i$.
\end{itemize}
\begin{tabbing}
sele\=ct ran\=dom $k_0\leftarrow\{0, 1\}^l$\\
for $j =1, 2, 3$\\
\> sender chooses $k_j$ at random from $\{0, 1\}^l$\\
\> sender and receiver run 1-2 Oblivious Transfer with\\
\>\> first input: $k_0\oplus\cdots\oplus k_{j-1}\oplus m_k$\\
\>\> second input: $k_j$
\end{tabbing}
If $i=j$, then receiver asks to receive the first input; otherwise, second input.\\
Receiver learns $k_i$ $\forall i\neq j$, with which, the receive can use to recovery $m_j$.\\\\
The algorithm is correct because it follows the OT protocol:
\begin{itemize}
\item sender has three messages
\item receiver is interested in one message, to which sender is oblivious
\item adversary's protocol runs in polynomial times (three, in this case)
\item in the end, receiver is able to compute the desired message
\end{itemize}
The protocol satisfies the privacy property: assuming the messages involved in the 1-2 OT exchange leak no information (see below), i.e. indistinguishable from random, then sender learns nothing about $i$, and receiver learns nothing beyond $x_i$.  This is because the protocol hinges upon the 1-2 OT protocol, which is defined to satisfy the privacy property.  Further, the messages involved in the 1-2 OT exchange are in fact indistinguishable from random because ${k_1, k_2, k_3}$ are all generated at random, and by definition, $x\oplus r$ for some $r\leftarrow \{0, 1\}^*$ is indistinguishable from random
\subsection{Part a}
The computation is correct, because, through a series of 1-2 OT exchanges, the receiver can recover $m_i$ given some $i$ that is oblivious to the sender.
\subsection{Part b}
The sender does not learn about the choice of $i$ because for all $j = 1, 2, 3$, the sender sends two messages and the receiver learns only one input.  The sender is oblivious to which one the receiver asked to receive.
\subsection{Part c}
The receiver learns only about $m_i$ because for all queries $j\neq i$, the receiver receives a random message $k_j$; the receiver only learns an obfuscated $m_i$ for $i = j$, which only happens once for any $i$.

\section{Problem 5} % (fold)
\label{sec:problem_5}
We follow the same procedure as the ZK protocol for graph isomorphism outlined in class.

\[\begin{array}{ll}
\mbox{Input:} & x=(G, H_1, H_2) \mbox{ where } |G|=|H_i| = n  \\
\mbox{Witness:} & \sigma such that \sigma(G) = H_1 \bigvee \sigma(G) = H_2\\
V\xleftarrow{H} P & \mbox{The prover chooses a random permutation $\pi$, computes $H\leftarrow \pi(G)$ and sends $H$}\\
V\xrightarrow{b} P & \mbox{The verifier picks a random bit $b$ and sends it.}\\
V\xleftarrow{\gamma} P & \mbox{If $b=0$, the prover sends $\pi$.  Otherwise, the prover sends $\gamma=\pi\cdot\sigma^{-1}$}\\
V & \mbox{Set $Z_i = (G, H_i)$; define $Z_i(0)=G$ and $Z_i(1)=H_i$.}\\ 
&\mbox{The verifier outputs 1 iff $\gamma(Z_0(b)) = H \bigvee \gamma(Z_1(b)) = H$}\\
P, V & \mbox{Repeat n times.}
\end{array} \]
Since we know from class that the graph isomorphism protocol is ZK, this modification is, by definition, also ZK, following the same proof.\\\\
Further, this protocol is correct because it shares the same correctness as the graph-isomorphism protocol, and essentially relaxes the constraint by adding an ``OR" condition in the verification step:
\[\mbox{The verifier outputs 1 iff $\gamma(Z_0(b)) = H \bigvee \gamma(Z_1(b)) = H$}\]
Further, if $G$ is isomorphic to either $H_1$ or $H_2$, then the verifier always accepts because $\pi(H)=G$ and $\sigma(\pi(H)) = \sigma(G) = H_1$ or $\sigma(\pi(H)) = \sigma(G) = H_2$.
% section problem_5 (end)


\section{Problem 6 (Bonus assigned in class)} % (fold)
\label{sec:problem_6}
Java Hash for strings:
\[T = \sum_{i} s\lbrack i\rbrack\times 31^{n-1}\]
It is fairly trivial to break the Java Hash as it is very easy to change the last two digits of a string to construct a collision, as the last two digits contribute $31\times s\lbrack n-1\rbrack + s\lbrack n\rbrack$ to the total sum.\\\\
For example, the following two strings should compute to the same hash code:
\begin{eqnarray*}
S &=& c_1\ldots c_{n-2}||\emph{00}\\
S &=& c_1\ldots c_{n-2}||\emph{1a}
\end{eqnarray*}
Since, in Java,
\begin{eqnarray*}
'0' &=& 48\\
'1'&=& 49\\
'a' &=&97\\
48 * 31 + 48 &=& 49 * 31 + 97
\end{eqnarray*}
These collisions are abundant and trivial to construct.
% section problem_6 (end)
\end{document}
